In many settings, it is necessary to certify certain data, as well as to revoke already issued certificates. For instance, in a Public-Key Infrastructure, (PKI) it is necessary to certify users' public keys.
In a digital signature scheme, each user U chooses a signing key SK.sub.u and a matching verification key, PK.sub.u. User U uses SK.sub.u to compute easily his digital signature of a message m, SIG.sub.u (m), while anyone knowing that PK.sub.u is U's public key can verify that SIG.sub.u (m) is U's signature of m. Finding SIG.sub.u (m) without knowing SK.sub.u is practically impossible. On the other hand, knowledge of PK.sub.u does not give any practical advantage in computing SK.sub.u. For this reason, it is in U's interest to keep SK.sub.u secret (so that only he can digitally sign for U) and to make PK.sub.u as public as possible (so that everyone dealing with U can verify U's digital signatures). At the same time, in a world with millions of users, it is essential in the smooth flow of business and communications to be certain that PK.sub.u really is the legitimate key of user U. To this end, users' public keys are "certified." At the same time it is also necessary to revoke some of the already-issued certificates.